/****   快 速 排 序 2021.4.13   ****/
#include <iostream>
#include <string.h>
#include <stack>
using namespace std;
/****   函数声明    ****/
int sortA(int *a ,int left ,int right);          // 挖坑法
int sortB(int *a ,int left ,int right);          // 前后指针法
int sortC(int *a ,int left ,int right);          // 左右指针法
void swap(int *a,int *b);                        // 交换函数
void QuickSort(int *a,int left ,int right);      // 快排递归函数
void QuickSortStack(int *a,int left ,int right); // 快排非递归函数

/**
 * 快速排序之 挖坑法
 *
 * @param a     待排数组
 * @param left  左边界
 * @param right 有边界
 * @return 基值索引
 */
int sortA(int *a ,int left ,int right){
    int k = a[left];
    while (left < right){
        while(a[right] >= k){
            right--;
        }
        a[left] = a[right];
        while(left < right && a[left] <= k){
            left++;
        }
        a[right] = a[left];
    }
    a[left] = k;
    return left;
}

 /**
 * 快速排序之 前后指针法
 *
 * @param a     待排数组
 * @param left  左边界
 * @param right 右边界
 * @return 基值索引
 */
int sortB(int *a ,int left ,int right){
    int p1 = left;
    int p2 = p1-1;
    if(left < right){
        while(p1 < right){
            if(a[p1] < a[right] && ++p2 != p1){
                swap(&a[p1],&a[p2]);
            }
            ++p1;
        }
        swap(&a[++p2],&a[right]);
    }
    return p2;
}

/**
 * 快速排序之 左右指针法
 *
 * @param a     待排数组
 * @param left  左边界
 * @param right 右边界
 * @return 基值索引
 */
int sortC(int *a ,int left ,int right){
    int k = right;
    int key = a[k];
    while(left < right){
        while(left < right && a[left] <= key){
            ++left;
        }
        while(left < right && a[right] >= key){
            --right;
        }
        swap(&a[left],&a[right]);
    }
    swap(&a[left],&a[k]);
    return left;
}

/**
 * 交换函数
 */
void swap(int *a ,int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 * 快排递归函数
 */
void QuickSort(int *a,int left ,int right){
    if(left < right){
        //int index = sortA(a, left, right);
        //int index = sortB(a, left, right);
        int index = sortC(a, left, right);
        QuickSort(a, left, index - 1);
        QuickSort(a, index + 1, right);
    }
 }

 /**
 * 快排非递归函数
 */
void QuickSortStack(int *a,int left ,int right){
    stack<int> s;
    if(left < right){
        s.push(left);
        s.push(right);
    }
    while(!s.empty()){
        int right = s.top();
        s.pop ();
        int left = s.top ();
        s.pop();
        int div = sortA(a,left,right);
        if(left < div-1){
            s.push (left);
            s.push (div-1);
        }
        if(div+1<right){
            s.push (div+1);
            s.push (right);
        }
    }
}

/**
 * 主函数
 */
int main(){
    int a[10] = {7, 29, 38, 4, 20, 3, 58, 2, 4, 16};
    cout<<"排序前：";
    for(int i = 0;i < 10;i++){
        cout<<a[i]<<"|";
    }
    //QuickSort(a,0,9);       //递归快排
    QuickSortStack(a,0,9);    //非递归快排
    cout<<"\n排序后：";
    for(int i = 0;i < 10;i++){
        cout<<a[i]<<"|";
    }
    return 0;
}